class Solution {
public:
    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
        // 先把 queries 数组按照 minSize 大小进行从大到小排序
        // 为什么要从大到小?
        // 当我们先把大的查询了，后面再有小的时候，前面大的已经添加到一个有序集合中了
        // 比如有两个询问，其中 minSize 分别为 3 和 6，我们可以先回答 minSize=6 的询问，再回答 minSize=3 的询问
        // 也就是先把面积 ≥6 的房间号添加到一个有序集合中，回答 minSize=6 的询问
        // 然后把面积 ≥3 的房间号添加到有序集合中，回答 minSize=3 的询问
        // 这里的关键是，由于面积 ≥6 的房间编号已经添加到有序集合中了
        // 所以后续只需把面积在 [3,5] 中的房间号添加到有序集合中，不需要重复处理面积 ≥6 的房间

        // 直接对 queries 排序是不行的，因为返回的答案必须按照询问的顺序
        // 解决办法：设 q 是 queries 的长度，创建一个下标数组 queryIds=[0,1,2,…,q−1]
        // 把下标根据 queries 的 minSize 从大到小排序，这样就避免直接对 queries 排序了

        int q = queries.size();
        vector<int> queryIds(q);
        iota(queryIds.begin(), queryIds.end(), 0);    // 从 0 自增的填充queryIds数组
        // 按照 minSize 从大到小排序
        ranges::sort(queryIds, {}, [&](int i) { return -queries[i][1]; });

        // rooms 数组也按照房间面积大小从大到小排序，方便处理有序集合，可以先把不存在 minSize 的查询过滤掉
        ranges::sort(rooms, {}, [&](auto &e) { return -e[1]; });

        vector<int> ans(q, -1);
        set<int> roomsIds;
        int j = 0;
        for(int &i : queryIds)
        {
            int preferredId = queries[i][0], minSize = queries[i][1];
            // 如果 queries 数组中要的面积太大，set 集合是不会有数据的
            while(j < rooms.size() && rooms[j][1] >= minSize)
            {
                roomsIds.insert(rooms[j][0]);
                j++;
            }

            int gap = INT_MAX;
            // lower_bound() 是一个二分查找
            auto it = roomsIds.lower_bound(preferredId);    // 在 set 中找到第一个大于等于 preferredId 的迭代器
            if(it != roomsIds.begin())
            {
                auto p = prev(it);
                gap = preferredId - *p;
                ans[i] = *p;
            }
            if(it != roomsIds.end() && *it - preferredId < gap)
            {
                // 右边的差更小
                ans[i] = *it;
            }
        }

        // 时间复杂度：O(nlogn + qlogq + qlogn)，其中 n 是 rooms 的长度，q 是 queries 的长度
        // 排序需要 O(nlogn + qlogq) 的时间，每次询问在 roomIds 上查找需要 O(logn) 的时间
        // 空间复杂度：O(n + q)

        return ans;
    }
};